1. Field of the Invention
The present invention generally relates to a wear leveling method, in particular, to a wear leveling method for a non-volatile memory and a controller using the same.
2. Description of Related Art
Along with the widespread of digital cameras, camera phones, and MP3 in recently years, the consumers' demand to storage media has increased drastically too. Flash memory is one of the most adaptable memories for such battery-powered portable products due to its characteristics such as data non-volatility, low power consumption, small volume, and non-mechanical structure. Besides being applied in foregoing portable products, flash memory is also broadly applied to external products such as flash cards and flash drives, and an even larger market is provided since one can have more than one flash card and flash drive. Thereby, flash memory has become one of the most focused electronic products in recent years.
Flash memory can offer such advantages as data rewritability and power-free data storage. However, blocks in a flash memory can be erased only a limited number of times, for example, a block in a flash memory is worn-out after being erased 10,000 times. Data loss may be caused when the storage capacity or performance of a flash memory is obviously deteriorated by its worn-out blocks.
The wear of a block in a flash memory is determined by the number of times this block is programmed or erased. In other words, the wear of a block is relatively low if the block is programmed (or written) only once; contrarily, the wear of a block is relatively higher if the block is programmed and erased repeatedly. For example, when a host keeps writing data into a flash memory by using the same logical block address (LBA), the block having the corresponding physical block address (PBA) in the flash memory is then repeatedly written and erased.
Generally speaking, the existence of worn-out blocks will reduce the performance of a flash memory even if the wear of other blocks are still relatively low. Besides the deterioration in the performance of the worn-out blocks, the performance of the entire flash memory is also reduced when the good blocks cannot provide enough space for storing data. In other words, when the number of worn-out blocks in a flash memory exceeds a threshold value, the flash memory is considered unusable even there are still good blocks. In this case, those good blocks are wasted.
Blocks in a flash memory should be used evenly in order to prolong the life of the flash memory. Blocks in a flash memory are usually grouped into a data area and a spare area. According to a conventional wear leveling method, blocks in the data area and blocks in the spare area are logically exchanged in an appropriate sequence at regular intervals, so that those blocks which are erased fewer times can be exchanged to the spare area to be programmed or written. However, such sequential exchange cannot guarantee that those blocks erased fewer times will be exchanged, and the exchanged blocks will be worn even more quickly if these blocks have been erased many times. As described above, the conventional wear leveling method is not very satisfactory.
Accordingly, a wear leveling method which can effectively prolong the life of a flash memory is to be provided.